package test.trie;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.apache.commons.collections4.CollectionUtils;

import lombok.Data;

public class TrieTree {
	
	Node root;
	
	public TrieTree() {
		root = new Node();
	}
	
	@Data
	static class Node {
		private Node parent;
		private List<Node> children = new ArrayList<>();
		private int count;
		private int deep;
		private char c;
		private String word = "";
		private boolean isLast;
		@Override
		public String toString() {
			return "Node [parent=" + (parent==null?null:parent.c) + ", count=" + count + ", deep=" + deep + ", c="
					+ c + ", word=" + word + ", isLast=" + isLast + "]";
		}
	}
	
	public void insert(String str) {
		char[] chars = str.toCharArray();
		
		Node parent = root;
		int i=0;
		while(true) {
			boolean isLast = (i == (chars.length - 1));
			char c = chars[i++];
			parent = searchAndAdd(c, parent, isLast);
			if(isLast) {
				break;
			}
		}
	}
	
	private Node searchAndAdd(char c, Node parent, boolean isLast) {
		List<Node> nodes = parent.children;
		Node result = null;
		for(Node node : nodes) {
			if(node.getC()==c) {
				result = node;
			}
		}
		if(result == null) {
			result = new Node();
			result.parent = parent;
			result.deep = parent.deep + 1;
			result.c = c;
			result.word = parent.word + c;
			parent.children.add(result);
		}
		if(isLast) {
			result.count++;
			result.isLast = true;
		}
		return result;
	}
	
	public Node search(char c, Node parent) {
		List<Node> nodes = parent.children;
		Node result = null;
		for(Node node : nodes) {
			if(node.getC()==c) {
				result = node;
			}
		}
		return result;
	}
	
	public Map<String, Integer> getAllWords() {
		Map<String, Integer> map = new HashMap<>();
		getChildren(map, root);
		return map;
	}
	
	private void getChildren(Map<String, Integer> map, Node parent) {
		if(CollectionUtils.isNotEmpty(parent.children)) {
			for(Node child : parent.children) {
				boolean isLast = child.isLast;
				if(isLast) {
					map.put(child.word, child.count);
				} else {
					getChildren(map, child);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		TrieTree tt = new TrieTree();
		Random random = new Random();
		
		for(int i=0;i<100;i++) {
			String word = "";
			for(int j=0;j<3;j++) {
				word += random.nextInt(10);
			}
			System.out.println(word);
			tt.insert(word);
		}
		
		System.out.println(tt.getAllWords());
//		System.out.println(tt.root.children.get(0).word);
//		System.out.println(tt.root.children.get(0).children.get(0).word);
//		System.out.println(tt.root.children.get(0).children.get(0).children.get(0).word);
	}

}
